# class Solution(object):
#     def maxSlidingWindow(self, nums, k):
#         """
#         :type nums: List[int]
#         :type k: int
#         :rtype: List[int]
#         """
#         s_list = []
#         res_list = []
#         n, n_a = divmod(len(nums), k)
#         if n <= 0:
#             res_list.append(max(nums))
#
#         res = (n - 1) * k + n_a + 1
#
#         for i in range(res):
#             s_list = nums[i:i + k]
#             res_list.append(max(s_list))
#         return res_list


class Solution(object):
    def maxSlidingWindow(self, nums, k):
        from collections import deque
        q = deque()
        ans = []
        for i, x in enumerate(nums):
            # 对除去,比当前数小的队列的值
            while q and nums[q[-1]] <= x:
                q.pop()
            
            ans.append(i)

            # 让队列始终保持,最新的窗口数
            if i -q[0] > k-1:
                q.popleft()
            
            if i >= k-1:
                ans.append(nums[q[0]])

        return ans

a = Solution()
b = a.maxSlidingWindow([1,3,-1,-3,5,3,6,7],3)
print(b)